package com.yusong.algorithm.retrospect;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 回溯法解决N皇后问题
 * https://leetcode-cn.com/submissions/detail/115903957/
 */
public class Queens {


    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] columns = new boolean[n];
        boolean[] slash1 = new boolean[2*n];
        boolean[] slash2 = new boolean[2*n];
        if(n <= 0){
            return result;
        }
        //数据初始化
        char[][] data = new char[n][n];
        for(int j = 0; j < n; j++){
            for(int i = 0; i < n ; i++){
                data[j][i] = '.';
            }
        }
        put(0,n,data,columns, slash1, slash2, result);
        return result;
    }


    //每行放一个进行回溯
    private void put(int index, int n, char[][] data, boolean[] columns , boolean[] slash1, boolean[] slash2, List<List<String>> result){
        if(index == n){
            List<String> thisResult = new ArrayList<>();
            for(int j = 0; j < n ; j++){
                char[] rowData = data[j];
                String rowStr = String.valueOf(rowData);
                thisResult.add(rowStr);
            }
            //System.out.println(thisResult);
            result.add(thisResult);
            return;
        }
        //循环试当前行每一个位置
        for(int i = 0 ; i < n; i++){
            //判断列是否可以放入1
            if(columns[i]){
                //System.out.println(index + " " + i +" | 无法放入，列存在");
                continue;
            }
            //斜线1，两数之和固定
            int slashVale1 = index + i;
            if(slash1[slashVale1]){
                //System.out.println(index + " " + i +" | 无法放入，斜线1存在");
                continue;
            }
            //斜线2，两数之差固定
            int slashVale2 = index - i + n;
            if(slash2[slashVale2]){
                //System.out.println(index + " " + i +" | 无法放入，斜线2存在");
                continue;
            }

            //放入，更新状态
            data[index][i] = 'Q';
            columns[i] = true;
            slash1[slashVale1] = true;
            slash2[slashVale2] = true;
            //递归：深度优先遍历
            //System.out.println(index + " " + i +" | 放入");
            put(index+1, n, data,  columns ,  slash1, slash2, result);
//            if( result.size() > 0){
//                break;
//            }
            //回归此次放入更新的状态
            data[index][i] = '.';
            columns[i] = false;
            slash1[slashVale1] = false;
            slash2[slashVale2] = false;
        }
    }

    public static void main(String[] args){
        Queens queens = new Queens();
        List<List<String>> result = queens.solveNQueens(4);
        System.out.println(result);
    }


}
